ff1588d761d55f48f61a52249e1dcc24

Micron Document

`:top

Auf dem Gebiet der `F33f`_`[Graphentheorie`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Graphentheorie]`_`f bezeichnet das `!Max-Flow-Min-Cut-Theorem`! einen `F33f`_`[Satz`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Satz_(Mathematik)]`_`f, der eine Aussage über den Zusammenhang von `F33f`_`[maximalen Flüssen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Flüsse_und_Schnitte_in_Netzwerken]`_`f und minimalen `F33f`_`[Schnitten`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Schnitt_(Graphentheorie)]`_`f eines `F33f`_`[Flussnetzwerkes`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Flussnetzwerk]`_`f gibt. Der Satz besagt:

`*Ein maximaler Fluss im Netzwerk hat genau den Wert eines minimalen Schnitts.`*

Der Satz ist eine Verallgemeinerung des `F33f`_`[Satzes von Menger`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Satz_von_Menger]`_`f. Er wurde im Jahr 1956 unabhängig von `F33f`_`[L.R. Ford Jr.`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Lester_Randolph_Ford_junior]`_`f und `F33f`_`[D.R. Fulkerson`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Delbert_Ray_Fulkerson]`_`f, sowie von `F33f`_`[P. Elias`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Peter_Elias]`_`f, A. Feinstein und `F33f`_`[C.E. Shannon`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Claude_Elwood_Shannon]`_`f bewiesen.`:cite-ref-ff-1-0[`F5bf`_`[1`#cite-note-ff-1]`_`f]`:cite-ref-2[`F5bf`_`[2`#cite-note-2]`_`f]

>>Contents

• `F0af`_`[Definitionen`#definitionen]`_`f

• `F0af`_`[Satz`#satz]`_`f

• `F0af`_`[Beweisskizze`#beweisskizze]`_`f

• `F0af`_`[Beispiel`#beispiel]`_`f

• `F0af`_`[Algorithmus zum Finden minimaler Schnitte`#algorithmus-zum-finden-minimaler-schnitte]`_`f

• `F0af`_`[Literatur`#literatur]`_`f

• `F0af`_`[Einzelnachweise`#einzelnachweise]`_`f

-─

>>Definitionen

Sei G ( V , E ) {\\displaystyle G(V,E)} ein endlicher `F33f`_`[gerichteter Graph`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Gerichteter_Graph]`_`f mit den `F33f`_`[Knoten`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Knoten_(Graphentheorie)]`_`f V {\\displaystyle V} und den `F33f`_`[Kanten`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Kante_(Graphentheorie)]`_`f E {\\displaystyle E} . Jede Kante ( u , v ) {\\displaystyle (u,v)} vom Knoten u {\\displaystyle u} zum Knoten v {\\displaystyle v} habe eine nichtnegative Kapazität c ( u , v ) . {\\displaystyle c(u,v).} Außerdem gibt es einen Quellknoten s {\\displaystyle s} , in dem der Netzwerkfluss beginnt, und einen Zielknoten t {\\displaystyle t} , in dem der Netzwerkfluss endet.

Ein Schnitt ist eine Aufteilung der Knoten in zwei disjunkte Teilmengen S {\\displaystyle S} und T {\\displaystyle T} für die gilt, s ∈ ∈ S {\\displaystyle s\\in S} und t ∈ ∈ T {\\displaystyle t\\in T} . Die Kapazität eines Schnittes ( S , T ) {\\displaystyle (S,T)} ist die Summe aller Kantenkapazitäten von S {\\displaystyle S} nach T {\\displaystyle T} , also

c ( S , T ) = ∑ ∑ u ∈ ∈ S , v ∈ ∈ T | ( u , v ) ∈ ∈ E c ( u , v ) {\\displaystyle c(S,T)=\\sum _{u\\in S,v\\in T|(u,v)\\in E}c(u,v)} .

>>Satz

Die folgenden drei Aussagen sind äquivalent:

1. f {\\displaystyle f} ist der maximale Fluss in G {\\displaystyle G} .

2. Das `F33f`_`[Residualnetzwerk`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Residualnetzwerk]`_`f G f {\\displaystyle G_{f}} enthält keinen `F33f`_`[augmentierenden Pfad`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Augmentierender_Pfad]`_`f.

3. Für mindestens einen Schnitt ( S , T ) {\\displaystyle (S,T)} ist der `F33f`_`[Wert`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Flüsse_und_Schnitte_in_Netzwerken]`_`f des Flusses gleich der `F33f`_`[Kapazität des Schnittes`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Flüsse_und_Schnitte_in_Netzwerken]`_`f: | f | = c ( S , T ) {\\displaystyle |f|=c(S,T)}

>>>Beweisskizze

• 1 ⇒ ⇒ 2 {\\displaystyle 1\\Rightarrow 2} Wenn es einen augmentierenden Pfad gäbe, so könnte man den Fluss entlang dessen vergrößern; somit kann der Fluss nicht maximal gewesen sein.

• 2 ⇒ ⇒ 3 {\\displaystyle 2\\Rightarrow 3} Wenn es keinen augmentierenden Pfad gibt, dann teile den Graph in S {\\displaystyle S} , die von s {\\displaystyle s} im Residualnetzwerk erreichbaren Knoten, und T {\\displaystyle T} , den Rest. Dann ist c ( S , T ) − − | f | = 0 {\\displaystyle c(S,T)-|f|=0} (wäre es nicht 0, so wäre T {\\displaystyle T} doch erreichbar gewesen). Dann ist für diesen Schnitt | f | = c ( S , T ) {\\displaystyle |f|=c(S,T)} .

• 3 ⇒ ⇒ 1 {\\displaystyle 3\\Rightarrow 1} Wenn f {\\displaystyle f} nicht maximal wäre, so könnte man ihn vergrößern. Da f {\\displaystyle f} kleiner gleich der Kapazität eines jeden Schnitts ist, kann für mindestens einen Schnitt die Kapazität noch nicht ausgenutzt sein; darüber hinaus gilt | f | = c ( S , T ) {\\displaystyle |f|=c(S,T)} für keinen Schnitt, weil sonst kein augmentierender Pfad für die Flussvergrößerung bestünde und der Fluss maximal wäre.

Insbesondere zeigt dies, dass der maximale Fluss gleich dem minimalen Schnitt ist: Wegen 3. hat er die Größe mindestens eines Schnitts, also mindestens des kleinsten, und wegen 2. auch höchstens diesen Wert, weil das Residualnetzwerk bereits keinen augmentierenden Pfad mehr enthalten kann, wenn | f | {\\displaystyle |f|} die Größe des kleinsten Schnitts erreicht hat.

>>Beispiel

Sei das Flussnetzwerk mit den Knoten V = { s , o , p , q , r , t } {\\displaystyle V=\\{s,o,p,q,r,t\\}} gegeben, und ein maximaler Fluss von der Quelle s {\\displaystyle s} zur Senke t {\\displaystyle t} der Größe 5.

Es gibt drei minimale Schnitte in diesem Netzwerk:

| Schnitt | Kapazität |

|---|---|

| S 1 = { s , p } , T = { o , q , r , t } {\\displaystyle S_{1}=\\{s,p\\},T=\\{o,q,r,t\\}} | c ( s , o ) + c ( p , r ) = 3 + 2 = 5 {\\displaystyle c(s,o)+c(p,r)=3+2=5} |

| S 2 = { s , o , p } , T = { q , r , t } {\\displaystyle S_{2}=\\{s,o,p\\},T=\\{q,r,t\\}} | c ( o , q ) + c ( p , r ) = 3 + 2 = 5 {\\displaystyle c(o,q)+c(p,r)=3+2=5} |

| S 4 = { s , o , p , q , r } , T = { t } {\\displaystyle S_{4}=\\{s,o,p,q,r\\},T=\\{t\\}} | c ( q , t ) + c ( r , t ) = 2 + 3 = 5 {\\displaystyle c(q,t)+c(r,t)=2+3=5} |

Anmerkung: Bei allen anderen Schnitten ist die Summe der `*Kapazitäten`* (nicht zu verwechseln mit dem Fluss) der ausgehenden Kanten größer gleich 6. Zum Beispiel ist S = { s , o } , T = { q , p , r , t } {\\displaystyle S=\\{s,o\\},T=\\{q,p,r,t\\}} kein minimaler Schnitt, da die Summe der Kapazitäten der ausgehenden Kanten gleich c ( o , q ) + c ( o , p ) + c ( s , p ) = 3 + 2 + 3 = 8 {\\displaystyle c(o,q)+c(o,p)+c(s,p)=3+2+3=8} ist. Des Weiteren ist S 5 = { s , o , p , r } , T = { q , t } {\\displaystyle S_{5}=\\{s,o,p,r\\},T=\\{q,t\\}} kein minimaler Schnitt, obwohl ( o , q ) {\\displaystyle (o,q)} und ( r , t ) {\\displaystyle (r,t)} voll genutzt werden; denn es gibt im Residualnetzwerk G f {\\displaystyle G_{f}} noch eine Kante (r,q) der Restkapazität c f ( r , q ) = c ( r , q ) − − f ( r , q ) = 0 − − ( − − 1 ) = 1 {\\displaystyle c_{f}(r,q)=c(r,q)-f(r,q)=0-(-1)=1} .

>>>Algorithmus zum Finden minimaler Schnitte

Es gibt verschiedene Algorithmen zum Finden minimaler Schnitte. Der folgende Algorithmus findet die Kanten eines minimalen Schnittes direkt aus dem Residualnetzwerk und macht sich damit die Eigenschaften des Max-Flow-Min-Cut-Theorems zu Nutze. Der Restflussgraph kann zum Beispiel mit Hilfe des `F33f`_`[Algorithmus von Ford und Fulkerson`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Algorithmus_von_Ford_und_Fulkerson]`_`f erzeugt werden.

`B100`F9d9`f`b

`B100`F9d9 G`f`b

`B100`F9d9 =`f`b

`B100`F9d9 (`f`b

`B100`F9d9 V`f`b

`B100`F9d9 ,`f`b

`B100`F9d9 E`f`b

`B100`F9d9 )`f`b

`B100`F9d9`f`b

`B100`F9d9 {\\displaystyle G=(V,E)}`f`b

`B100`F9d9`f`b

`B100`F9d9 ein endlicher gerichteter Graph mit einer Quelle`f`b

`B100`F9d9`f`b

`B100`F9d9 s`f`b

`B100`F9d9`f`b

`B100`F9d9 {\\displaystyle s}`f`b

`B100`F9d9`f`b

`B100`F9d9, einer Senke`f`b

`B100`F9d9`f`b

`B100`F9d9 t`f`b

`B100`F9d9`f`b

`B100`F9d9 {\\displaystyle t}`f`b

`B100`F9d9`f`b

`B100`F9d9 und jede Kante habe eine nichtnegative Kapazität.`f`b

`B100`F9d9findeKantenEinesMinCut(`f`b

`B100`F9d9`f`b

`B100`F9d9 G`f`b

`B100`F9d9`f`b

`B100`F9d9 {\\displaystyle G}`f`b

`B100`F9d9`f`b

`B100`F9d9)`f`b

`B100`F9d91`f`b

`B100`F9d9`f`b

`B100`F9d9 G`f`b

`B100`F9d9`f`b

`B100`F9d9 f`f`b

`B100`F9d9`f`b

`B100`F9d9 ←`f`b

`B100`F9d9`f`b

`B100`F9d9 {\\displaystyle G_{f}\\leftarrow }`f`b

`B100`F9d9`f`b

`B100`F9d9Residualnetzwerk(`f`b

`B100`F9d9`f`b

`B100`F9d9 G`f`b

`B100`F9d9`f`b

`B100`F9d9 {\\displaystyle G}`f`b

`B100`F9d9`f`b

`B100`F9d9)`f`b

`B100`F9d92`f`b

`B100`F9d9`f`b

`B100`F9d9 S`f`b

`B100`F9d9 ←`f`b

`B100`F9d9 ∅`f`b

`B100`F9d9`f`b

`B100`F9d9 {\\displaystyle S\\leftarrow \\emptyset }`f`b

`B100`F9d9`f`b

`B100`F9d93`f`b

`B100`F9d9`f`b

`B100`F9d9 T`f`b

`B100`F9d9 ←`f`b

`B100`F9d9 ∅`f`b

`B100`F9d9`f`b

`B100`F9d9 {\\displaystyle T\\leftarrow \\emptyset }`f`b

`B100`F9d9`f`b

`B100`F9d94 Für jeden Knoten`f`b

`B100`F9d9`f`b

`B100`F9d9 v`f`b

`B100`F9d9 ∈`f`b

`B100`F9d9 V`f`b

`B100`F9d9`f`b

`B100`F9d9 {\\displaystyle v\\in V}`f`b

`B100`F9d9`f`b

`B100`F9d95 Wenn Pfad(`f`b

`B100`F9d9`f`b

`B100`F9d9 s`f`b

`B100`F9d9 ,`f`b

`B100`F9d9 v`f`b

`B100`F9d9`f`b

`B100`F9d9 {\\displaystyle s,v}`f`b

`B100`F9d9`f`b

`B100`F9d9) in`f`b

`B100`F9d9`f`b

`B100`F9d9 G`f`b

`B100`F9d9`f`b

`B100`F9d9 f`f`b

`B100`F9d9`f`b

`B100`F9d9 {\\displaystyle G_{f}}`f`b

`B100`F9d9`f`b

`B100`F9d9 existiert`f`b

`B100`F9d96 dann`f`b

`B100`F9d9`f`b

`B100`F9d9 S`f`b

`B100`F9d9 ←`f`b

`B100`F9d9 S`f`b

`B100`F9d9 ∪`f`b

`B100`F9d9 {`f`b

`B100`F9d9 v`f`b

`B100`F9d9 }`f`b

`B100`F9d9`f`b

`B100`F9d9 {\\displaystyle S\\leftarrow S\\cup \\{v\\}}`f`b

`B100`F9d9`f`b

`B100`F9d97 ansonsten`f`b

`B100`F9d9`f`b

`B100`F9d9 T`f`b

`B100`F9d9 ←`f`b

`B100`F9d9 T`f`b

`B100`F9d9 ∪`f`b

`B100`F9d9 {`f`b

`B100`F9d9 v`f`b

`B100`F9d9 }`f`b

`B100`F9d9`f`b

`B100`F9d9 {\\displaystyle T\\leftarrow T\\cup \\{v\\}}`f`b

`B100`F9d9`f`b

`B100`F9d98`f`b

`B100`F9d9`f`b

`B100`F9d9 C`f`b

`B100`F9d9 ←`f`b

`B100`F9d9 ∅`f`b

`B100`F9d9`f`b

`B100`F9d9 {\\displaystyle C\\leftarrow \\emptyset }`f`b

`B100`F9d9`f`b

`B100`F9d99 Für jede Kante`f`b

`B100`F9d9`f`b

`B100`F9d9 e`f`b

`B100`F9d9 ∈`f`b

`B100`F9d9 E`f`b

`B100`F9d9`f`b

`B100`F9d9 {\\displaystyle e\\in E}`f`b

`B100`F9d9`f`b

`B100`F9d910 Wenn startKnoten(`f`b

`B100`F9d9`f`b

`B100`F9d9 e`f`b

`B100`F9d9`f`b

`B100`F9d9 {\\displaystyle e}`f`b

`B100`F9d9`f`b

`B100`F9d9)`f`b

`B100`F9d9`f`b

`B100`F9d9 ∈`f`b

`B100`F9d9 S`f`b

`B100`F9d9`f`b

`B100`F9d9 {\\displaystyle \\in S}`f`b

`B100`F9d9`f`b

`B100`F9d9 und endKnoten(`f`b

`B100`F9d9`f`b

`B100`F9d9 e`f`b

`B100`F9d9`f`b

`B100`F9d9 {\\displaystyle e}`f`b

`B100`F9d9`f`b

`B100`F9d9)`f`b

`B100`F9d9`f`b

`B100`F9d9 ∈`f`b

`B100`F9d9 T`f`b

`B100`F9d9`f`b

`B100`F9d9 {\\displaystyle \\in T}`f`b

`B100`F9d9`f`b

`B100`F9d9 liegt`f`b

`B100`F9d911 dann`f`b

`B100`F9d9`f`b

`B100`F9d9 C`f`b

`B100`F9d9 ←`f`b

`B100`F9d9 C`f`b

`B100`F9d9 ∪`f`b

`B100`F9d9 {`f`b

`B100`F9d9 e`f`b

`B100`F9d9 }`f`b

`B100`F9d9`f`b

`B100`F9d9 {\\displaystyle C\\leftarrow C\\cup \\{e\\}}`f`b

`B100`F9d9`f`b

`B100`F9d912`f`b

`B100`F9d9`f`b

`B100`F9d9 C`f`b

`B100`F9d9`f`b

`B100`F9d9 {\\displaystyle C}`f`b

`B100`F9d9`f`b

`B100`F9d9 ist jetzt die Menge der Kanten für einen minimalen Schnitt`f`b

C {\\displaystyle C} würde im oberen Beispiel die Schnittkanten von S 1 {\\displaystyle S_{1}} enthalten.

>>Literatur

• Thomas H. Cormen, `F33f`_`[Charles E. Leiserson`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Charles_E._Leiserson]`_`f, `F33f`_`[Ronald L. Rivest`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Ronald_L._Rivest]`_`f, Clifford Stein: `*Introduction to Algorithms`*. Second Edition. MIT Press and McGraw-Hill, 2001, ISBN 0-262-03293-7. Chapter 26: `*Maximum Flow`*, S. 643–700.

• Santanu Saha Ray: Graph Theory with Algorithms and its Applications. Springer India, New Delhi u. a. 2013, ISBN 978-81-322-0749-8, S. 162–165.

>>Einzelnachweise

`:cite-note-ff-1`!1.`! `F0af`_`[↑`#cite-ref-ff-1-0]`_`f L.R. Ford Jr., D.R Fulkerson: Maximal flow through a network. In: Canad. J. Math. 8. Jahrgang, 1956, S. 399–404, `F33f`_`[doi`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Digital_Object_Identifier]`_`f:10.4153/CJM-1956-045-5 (math.ca [PDF]).

`:cite-note-2`!2.`! `F0af`_`[↑`#cite-ref-2]`_`f P. Elias, A. Feinstein, C.E. Shannon: Note on Maximum Flow Through a Network. In: IRE Trans. on Information Theory, IT. 2. Jahrgang, Nr. 4, 1956, S. 117–119, `F33f`_`[doi`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Digital_Object_Identifier]`_`f:10.1109/TIT.1956.1056816 (ece.rice.edu (`F33f`_`[Memento`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Webarchivierung]`_`f des Originals vom 4. März 2016 im `*`F33f`_`[Internet Archive`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Internet_Archive]`_`f`*) [abgerufen am 3. September 2013]).

`c`F0af`_`[↑ Back to top`#top]`_`f`a